We describe a systematic program aimed at identifying and characterizing candidate high-mass proto-stellar objects (HMPOs). Our candidate sample consists of 69 objects selected by criteria based on those established by Ramesh & Sridharan (1997) using far-infrared, radio-continuum and molecular line data. Infrared-Astronomical-Satellite (IRAS) and Midcourse-Space-Experiment (MSX) data were used to study the larger scale environments of the candidate sources and to determine their total luminosities and dust temperatures. To derive the physical and chemical properties of our target regions, we observed continuum and spectral line radiation at millimeter and radio wavelengths. We imaged the free-free and dust continuum emission at wavelengths of 3.6 cm and 1.2 mm, respectively, searched for H2O and CH3OH maser emission and observed the CO 2-1 and several NH3 lines toward all sources in our sample. Other molecular tracers were observed in a subsample. The presented results indicate that a substantial fraction of our sample harbors HMPOs in a pre-UCHII region phase, the earliest known stage in the high-mass star formation process.